// Task: Implement a struct named 'RangeList'
// A pair of integers define a range, for example: [1, 5). This range includes integers: 1, 2, 3, and 4.
// A range list is an aggregate of these ranges: [1, 5), [10, 11), [100, 201)
// NOTE: Feel free to add any extra member variables/functions you like.
package main

import (
	"errors"
	"fmt"

	"github.com/emirpasic/gods/maps/treemap"
)

// RangeList 区间列表对象
type RangeList struct {
	tree *treemap.Map // 存储区间使用的红黑树
}

// RangeValue 红黑树区间节点的值对象 left -> {right, color}
type RangeValue struct {
	right int  // 区间右端点
	color bool // 该区间是是黑色（真）还是白色（假）
}

const (
	MinPos            = 1           // 维护的数轴的左端点
	MaxPos            = 1<<31 - 1   // 维护的数轴的右端点
	black, white bool = true, false // 区间的颜色
	notVis            = -1          // 未访问标记
)

// NewRangeList 初始化一个 RangeList
func NewRangeList() *RangeList {
	rangeList := &RangeList{treemap.NewWithIntComparator()} // 初始化红黑树
	rangeList.tree.Put(MinPos, RangeValue{MaxPos, false})   // 将整个数轴覆盖为白色
	return rangeList
}

// split 根据指定的分割点判断红黑树中是否存在需要被分割的区间，如是则分割
func (rangeList *RangeList) split(pos int) {
	targetLeft, targetVal := rangeList.tree.Floor(pos) // 找到第一个左端点大于等于分割点的区间
	if targetLeft == pos || targetLeft == nil {        // 如果找到的区间左端点恰好位于分割点或不存在，则无需分割
		return
	}
	targetRight := targetVal.(RangeValue).right // 待拆分区间的右端点
	targetColor := targetVal.(RangeValue).color // 待拆分区间的颜色

	if targetRight < pos { // 如果前驱节点右端点在分割点左侧，则与其不交，无需分割
		return
	}

	rangeList.tree.Remove(targetLeft) // 移除原区间

	rangeList.tree.Put(targetLeft, RangeValue{pos - 1, targetColor}) // 加入拆分后的左区间
	rangeList.tree.Put(pos, RangeValue{targetRight, targetColor})    // 加入拆分后的右区间
}

// assign 把一个左开右闭的区间分配上某种颜色
func (rangeList *RangeList) assign(left, right int, color bool) {
	rangeList.split(right) // 先对右端点拆分区间
	rangeList.split(left)  // 再对左端点拆分区间（以保证不漏过新拆分形成的区间）

	// 将新区间覆盖的区域全部擦除，以维护树上区间无交集
	for key, _ := rangeList.tree.Ceiling(left); key != nil && key.(int) < right; key, _ = rangeList.tree.Ceiling(key) {
		rangeList.tree.Remove(key)
	}

	rangeList.tree.Put(left, RangeValue{right - 1, color}) // 插入新区间
}

// Add 向 RangeList 中加入一个左开右闭的区间
func (rangeList *RangeList) Add(rangeElement [2]int) error {
	left, right := rangeElement[0], rangeElement[1]
	if left >= right { // 区间不合法
		return errors.New("range element error")
	} else { // 区间合法
		rangeList.assign(left, right, black)
	}
	return nil
}

// Remove 向 RangeList 中移除一个左开右闭的区间
func (rangeList *RangeList) Remove(rangeElement [2]int) error {
	left, right := rangeElement[0], rangeElement[1]
	if left >= right { // 区间不合法
		return errors.New("range element error")
	} // 区间合法
	rangeList.assign(left, right, white)
	return nil
}

// Print 输出 RangeList 中的区间
// 由于并不真的合并区间，所以会在输出时进行伪合并
func (rangeList *RangeList) Print() {
	l, r := notVis, notVis                                // 输出的区间的左右端点，初始化为数轴以外的值作为未访问标记
	for iter := rangeList.tree.Iterator(); iter.Next(); { // 遍历红黑树
		v := iter.Value().(RangeValue) // 当前区间的 RangeValue （包含右端点和颜色）
		nowLeft := iter.Key().(int)    // 当前区间左端点
		nowRight := v.right            // 当前区间右端点
		if v.color == black {          // 如果是黑色区间（即存在区间）
			if l == notVis { // 如果未访问，即说明该区间左侧不存在与之相连的区间，直接赋值
				l = nowLeft
				r = nowRight
			} else if nowLeft == r+1 { // 如果当前区间左端点和上一区间右端点相邻，则拼接两区间
				r = nowRight
			} else { // 如果当前区间左端点和上一区间右端点不相邻，则输出上一区间，并替代区间
				fmt.Printf("[%v,%v) ", l, r+1)
				l = nowLeft
				r = nowRight
			}
		} else {             // 如果是白色区间（即不存在的区间）
			if l != notVis { // 如果存在未输出的区间，而当前区间不可以与之拼接，故直接输出并将其重新初始化
				fmt.Printf("[%v,%v) ", l, r+1)
				l = notVis
			}
		}
	}
	if l != notVis { // 如果即存在未输出的区间
		fmt.Printf("[%v,%v) ", l, r+1)
	}
	fmt.Printf("\n") // 单次输出完毕，换行
}

func main() {
	rl := NewRangeList()
	rl.Add([2]int{1, 5})
	rl.Print()
	// Should display: [1, 5)
	rl.Add([2]int{10, 20})
	rl.Print()
	// Should display: [1, 5) [10, 20)
	rl.Add([2]int{20, 20})
	rl.Print()
	// Should display: [1, 5) [10, 20)
	rl.Add([2]int{20, 21})
	rl.Print()
	// Should display: [1, 5) [10, 21)
	rl.Add([2]int{2, 4})
	rl.Print()
	// Should display: [1, 5) [10, 21)
	rl.Add([2]int{3, 8})
	rl.Print()
	// Should display: [1, 8) [10, 21)
	rl.Remove([2]int{10, 10})
	rl.Print()
	// Should display: [1, 8) [10, 21)
	rl.Remove([2]int{10, 11})
	rl.Print()
	// Should display: [1, 8) [11, 21)
	rl.Remove([2]int{15, 17})
	rl.Print()
	// Should display: [1, 8) [11, 15) [17, 21)
	rl.Remove([2]int{3, 19})
	rl.Print()
	// Should display: [1, 3) [19, 21)
}
